1. Field of the Invention
The invention relates generally to the field of packet-switched networks, and in particular to techniques for managing packet traffic inside a router or switch.
2. Background Art
Today, sending information using packets over communications networks, such as the Internet, is widespread. All forms of data including email, documents, photos, video, audio, software updates, are sent via communications lines connected together by routers or switches. The increased data flow has created the need for higher capacity, such as 10 gigabits-per-second (Gbps), network lines. This in turn means that the routers or switches must route these data packets from source to destination in an efficient manner and not become bottlenecks hindering data flow.
FIG. 1 gives an example of a conventional router 100 (or switch). The router 100 takes packets received through its N input (or ingress) ports, e.g., input port 1 110, input port 2 112, input port 3 114, to input port N 116 and routes them via switching fabric 140 to the appropriate M output (or egress) ports, e.g., output port 1 170 through output port M 174 according to commands received from a routing processor 160. The switching fabric 140 in the router 100 is a switching network. Each input port has one or more queues. For example, input port 1 110 shows a queue 120-1 which has an arrival rate of packets 122-1, and a service rate μ 124-1, which represents the rate the data is sent or transmitted out of the queue 120-1. While FIG. 1 shows only one queue for input port 1 110, the number of queues shown at input port 1 110 is for illustration purposes only and there may be one or more queues per each input port. The output ports typically have one or more output queue per port. For example, in output port 1 170, there is a queue 174 with an arrival rate data of 172 and a service or send data rate of 176. In a conventional router M=N.
An issue of bandwidth allocation occurs when a plurality of input queues send data to a shared output queue. For example, assume that input port 1 110 has input queue 120-1, that input port 2 112 has input queue 120-2, and that input port 3 114 has input queue 120-3. Further assume that they share via switching fabric 140 a common output port queue 174. The send rates, μi, associated with the data lines 126, 128, 130, i.e., μ1, μ2, and μ3, respectively, cannot exceed the maximum arrival rate R 172 of output queue 174. Thus data line 150 which has as its rate, the sum of μ1, μ2, μ3 cannot exceed R. The issue in this example is in the allocation of the bandwidth of data line 150 to each of the lines 126, 128, and 130. For example, a poor allocation would give all the available bandwidth to the first two data lines 126 and 128 (input queues 120-1 and 120-2). This would mean the queue 120-3 in input port 3 114 would starve. Thus some form of “fair” allocation between the input queues of the available bandwidth of the shared output queue is needed.
Currently, there are many algorithms for routing data traffic, but each has its own sets of limitations and problems. One example is a rate controlled service discipline, which includes a rate controller and a scheduler. The rate controller has a set of regulators corresponding to each of the connections traversing the switch. The regulators shape the input traffic by assigning an eligibility time to each packet. The scheduler orders the transmission of eligible packets from all the connections. There are several problems with this algorithm. First, the system may be idle even when there are packets waiting to be sent. Next, the single scheduler is a single point of failure. Another example is a conventional shared memory approach, that depends upon a central switch to provide high-speed interconnections to all ports. The problem is that each packet must be examined to determine its routing. Thus this approach requires a very high memory bandwidth and a fairly high overhead even for small systems.
Therefore with the increasing demand for routers that can switch high rates of data, for example, about 10 Gbps, at each input port, there is a need for techniques which efficiently and fairly control the data flow in a router.